The overall objective is to develop efficient algorithms and software tools for the analysis of genetic variation in human populations and its association with phenotypic variation. Correlating variations in DMAsequences with phenotypic differences has been one of the grand challenges in biomedical research. With the completion of the human genome project, substantial effort has been made to identify all common genetic variations such as single nucleotide polymorphisms (SNPs). While millions of SNPs have been identified, there is a great need for models and tools to characterize genetic variation in humans, and to facilitate the localization of genes underling complex diseases/traits. To meet the need, we propose to develop novel algorithmic approaches and softwaretools to address some of the fundamental issues in the analysis of SNPs and haplotypes with applications in gene association mapping. More specifically, we propose to devise efficient and robust algorithms to infer haplotypes from genotypes on a pedigree, impute missing SNPs, discover the haplotype structure, and select informative (tag) SNPs. We will also develop computational models that could utilize haplotypes in the identification of disease genes. The focus of this proposal is the development of novel combinatorial algorithms, datamining approaches, statistical techniques, as well as robust and user friendly tools. The emphasis is on the efficiency of algorithms because existing methods could not handle data sets at the whole genome level. The algorithms will be performedon the public databases (e.g. the HapMap project), as well as other human data generated in our collaborators' ongoing projects, including data sets concerning various complications of pregnancy, modifier genes of the cystic fibrosis disease and the genetic effects of late-onset Alzheimer disease. We anticipate that this project will result in a full spectrum of efficient and effective algorithms and softwaretools that will be useful to the broad biomedical research community and will greatly facilitate the study of human genetic variation and its association with complex diseases/traits. The proposed project fits well in two of the three themes that NIH has identified in its Roadmap initiatives: research in bioinformatics and computational biology under the theme of New Pathways to Discovery and interdisciplinary research under the theme of ResearchTeams of the Future.